package com.company.algo.graph;

import java.util.Arrays;
import java.util.Scanner;

//最短路径 HDU-2544
public class Dijkstra {
    static int[][] map = new int[101][101];
    static int[] dis = new int[101];

    public static void initMap() {
        for (int[] a : map) {
            Arrays.fill(a, Integer.MAX_VALUE >> 2);
        }
    }

    public static void main(String[] args) {
        //读取输入
        Scanner sc = new Scanner(System.in);
        int n, m;
        while (sc.hasNext() && (n = sc.nextInt()) != 0) {
            initMap();
            m = sc.nextInt();
            for (int i = 0; i < m; i++) {
                int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
                if (map[u][v] > w) {
                    map[u][v] = w;
                    map[v][u] = w;
                }
            }
            dijkstra(1, n);
            System.out.println(dis[n]);
        }
    }

    //求源点s到其他点的最短路径
    private static void dijkstra(int s, int n) {
        Arrays.fill(dis, s + 1, dis.length, Integer.MAX_VALUE >> 2);    //dis[1]=0，其余为正无穷
        boolean[] selected = new boolean[101];
        while (true) {
            int min_idx = 0, min_w = Integer.MAX_VALUE >> 2;
            for (int j = 1; j <= n; j++) {
                if (!selected[j] && min_w > dis[j]) {
                    min_idx = j;
                    min_w = dis[j];
                }
            }
            if (min_idx == 0) break;        //如果没有可选的点，直接结束
            selected[min_idx] = true;       //将当前点设置为已选择
            for (int i = 1; i <= n; i++) {
                if (!selected[i] && dis[i] > dis[min_idx] + map[min_idx][i])
                    dis[i] = dis[min_idx] + map[min_idx][i];
            }
        }
    }
}
